package com.neusoft.recursion.maze;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 迷宫: 递归案例实现类
 * @date 2024-10-21
 */
public class MazeRecursion {

    public static void main(String[] args) {
        int[][] mazeArray = initMaze();
        /*
         * 1、小球起点: mazeArray[1][1]
         * 2、小球终点: mazeArray[6][5]
         * 3、【1】: 墙；【2】: 通路可以走；【3】: 该点已经走过，但是走不通
         * 4、走迷宫时确定一个策略顺序,如果该点走不通，再回溯
         */
        // 小球递归走地图查找终点: 【先下->不通则右->不通则上->不通则左】
        if (setWayStrategy1(mazeArray, 1, 1)) {
            printMaze(mazeArray);
        }

        // 小球递归走地图查找终点: 【先右->不通则下->不通则左->不通则上】
        mazeArray = initMaze();
        if (setWayStrategy2(mazeArray, 1, 1)) {
            printMaze(mazeArray);
        }
    }

    /**
     * 初始化迷宫的数据结构
     *
     * @return 迷宫地图数组
     */
    public static int[][] initMaze() {
        // 先创建一个二维数组，模拟迷宫: 长8行, 宽7列。 使用1表示墙【不能走】, 0表示路【可以走】
        int[][] mazeArray = new int[8][7];

        // 第一行、最后一行全部设置为1【墙】
        for (int i = 0; i < 7; i++) {
            mazeArray[0][i] = 1;
            mazeArray[7][i] = 1;
        }
        // 第一列、最后一列全部设置为1【墙】
        for (int i = 0; i < 8; i++) {
            mazeArray[i][0] = 1;
            mazeArray[i][6] = 1;
        }

        // 设置挡板【墙】【不能走】
        mazeArray[3][1] = 1;
        mazeArray[3][2] = 1;
        printMaze(mazeArray);

        return mazeArray;
    }

    /**
     * 使用递归回溯来给小球找路: 【先下->不通则右->不通则上->不通则左】
     *
     * @param mazeArray 迷宫地图
     * @param xAxis     小球起点: x坐标
     * @param yAxis     小球起点: y坐标
     * @return 能否找到出路的标志
     */
    public static boolean setWayStrategy1(int[][] mazeArray, int xAxis, int yAxis) {
        if (mazeArray[6][5] == 2) {
            // 通路已经找到
            return true;
        }
        if (mazeArray[xAxis][yAxis] == 0) {
            // 当前这个点还没有走过, // 按策略【先下->不通则右->不通则上->不通则左】走
            // 假定该点是可以走通
            mazeArray[xAxis][yAxis] = 2;

            if (setWayStrategy1(mazeArray, xAxis + 1, yAxis)) {
                // 向下走
                return true;
            } else if (setWayStrategy1(mazeArray, xAxis, yAxis + 1)) {
                // 向右走
                return true;
            } else if (setWayStrategy1(mazeArray, xAxis - 1, yAxis)) {
                // 向上走
                return true;
            } else if (setWayStrategy1(mazeArray, xAxis, yAxis - 1)) {
                // 向左走
                return true;
            } else {
                // 说明该点是走不通，是死路
                mazeArray[xAxis][yAxis] = 3;
                return false;
            }
        } else {
            // 如果mazeArray[xAxis][yAxis] != 0, 可能是1、2、3
            return false;
        }
    }

    /**
     * 使用递归回溯来给小球找路: 【先右->不通则下->不通则左->不通则上】
     *
     * @param mazeArray 迷宫地图
     * @param xAxis     小球起点: x坐标
     * @param yAxis     小球起点: y坐标
     * @return 能否找到出路的标志
     */
    public static boolean setWayStrategy2(int[][] mazeArray, int xAxis, int yAxis) {
        if (mazeArray[6][5] == 2) {
            // 通路已经找到
            return true;
        }
        if (mazeArray[xAxis][yAxis] == 0) {
            // 当前这个点还没有走过, // 按策略【先下->不通则右->不通则上->不通则左】走
            // 假定该点是可以走通
            mazeArray[xAxis][yAxis] = 2;

            if (setWayStrategy2(mazeArray, xAxis, yAxis + 1)) {
                // 向右走
                return true;
            } else if (setWayStrategy2(mazeArray, xAxis + 1, yAxis)) {
                // 向下走
                return true;
            } else if (setWayStrategy2(mazeArray, xAxis, yAxis - 1)) {
                // 向左走
                return true;
            } else if (setWayStrategy2(mazeArray, xAxis - 1, yAxis)) {
                // 向上走
                return true;
            } else {
                // 说明该点是走不通，是死路
                mazeArray[xAxis][yAxis] = 3;
                return false;
            }
        } else {
            // 如果mazeArray[xAxis][yAxis] != 0, 可能是1、2、3
            return false;
        }
    }

    /**
     * 打印迷宫地图
     *
     * @param mazeArray 迷宫地图
     */
    public static void printMaze(int[][] mazeArray) {
        System.out.println("迷宫地图: 跟maze.png做比较");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(mazeArray[i][j] + " ");
            }
            System.out.println();
        }
    }
}
